#pragma once

#include "../../nonos/mcus/phy62xx/std_type.h"


// forwards
template<typename T> class LinkedList;

template<typename T> class LinkedListItem {
	friend LinkedList<T>;

	protected: LinkedList<T> *_owner=NULL;
	protected: LinkedListItem<T> *_prev=NULL, *_next=NULL;
	protected: T _value;

	protected: LinkedListItem(LinkedList<T> *owner, T value) { _owner = owner; _value = value; }
	protected: virtual ~LinkedListItem() { remove(); }

	public: T get() { return _value; }
	public: void set(T value) { _value = value; }

	public: LinkedListItem<T>* next() { return _next; }
	public: LinkedListItem<T>* prev() { return _prev; }
	public: void remove() { _owner->remove(this); }
	public: void insertBeforeMe(T val)  { _owner->insertBefore(this, val); }
	public: void insertAfterMe(T val) { _owner->insertAfter(this, val); }
};

template<typename T> class LinkedList {
	friend LinkedListItem<T>;

	protected: LinkedListItem<T> *_head=NULL, *_tail=NULL;
	protected: int _count = 0;

	public: virtual ~LinkedList() { clear(); }

	public: int size() { return _count; }
	public: LinkedListItem<T>* head() { return _head; }
	public: LinkedListItem<T>* tail() { return _tail; }
	public: void popHead() { remove(_head); }
	public: void popTail() { remove(_tail); }
	public: void pushHead(T value) { insertBefore(_head, value); }
	public: void pushTail(T value) { insertAfter(_tail, value); }
	public: void clear() { while(_tail) { remove(_tail); } }

	protected: void insertBefore(LinkedListItem<T>* curr, T& value) __attribute__ ((noinline)) {
		LinkedListItem<T> *theNew = new LinkedListItem<T>(this, value);
		if(curr) {
			// 之前已经有了
			theNew->_prev = curr->_prev;
			theNew->_next = curr;
			curr->_prev = theNew;
			if(theNew->_prev) {
				// 前面还有
				theNew->_prev->_next = theNew;
			} else {
				// 前面没有了
				_head = theNew;
			}
		} else {
			// 这是第一个
			_head= _tail = theNew;
			theNew->_prev = theNew->_next = NULL;
		}
		_count++;
	}

	protected: void insertAfter(LinkedListItem<T>* curr, T& value) __attribute__ ((noinline)) {
		LinkedListItem<T> *theNew = new LinkedListItem<T>(this, value);
		if(curr) {
			// 之前已经有了
			theNew->_prev = curr;
			theNew->_next = curr->_next;
			curr->_next = theNew;
			if(theNew->_next) {
				// 后面还有
				theNew->_next->_prev = theNew;
			} else {
				// 后面没有了
				_tail = theNew;
			}
		} else {
			// 这是第一个
			_head= _tail = theNew;
			theNew->_prev = theNew->_next = NULL;
		}
		_count++;
	}

	protected: void remove(LinkedListItem<T> *item) __attribute__ ((noinline)) {
		if(_count == 0) return;
		if(item->_next) {
			// 如果后面有，则后面的那个 向前指向 自己前面那个
			item->_next->_prev = item->_prev;
		} else {
			// 如果后面没有了，则自己前面的那个就是最后一个
			_tail = item->_prev;
		}

		if(item->_prev) {
			// 如果前面有，则前面的那个 向后指向 自己后面那个
			item->_prev->_next = item->_next;
		} else {
			// 如果前面没有了，则自己后面的那个就是第一个
			_head = item->_next;
		}

		// 现在可以安全地删除自己了
		delete(item);
		_count--;
	}
};
